package com.yanceysong.codetop.s91_s100;

import com.yanceysong.common.ListNode;

public class S98_Mid_24_两两交换链表中的节点 {
    /**
     * .S98_Mid_24_两两交换链表中的节点
     * .<p>
     * .<a href="https://leetcode.cn/problems/swap-nodes-in-pairs/">...</a>
     * .<p>
     * .给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
     * .你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * .<p>
     * .示例：
     * .<p>
     * .输入：head = [1,2,3,4]
     * .输出：[2,1,4,3]
     * .<p>
     * .输入：head = []
     * .输出：[]
     * .<p>
     * .输入：head = [1]
     * .输出：[1]
     * .<p>
     * .提示：
     * .<p>
     * .链表中节点的数目在范围 [0, 100] 内
     * .0 <= Node.val <= 100
     * .<p>
     * .核心标签：链表、递归、迭代
     * .<p>
     * .算法原理：迭代法（使用虚拟头节点）
     * .- 创建一个虚拟头节点（dummy node），指向链表头部
     * .- 使用一个指针 prev 指向当前需要交换的两个节点的前一个节点
     * .- 每次交换相邻的两个节点：node1 和 node2
     * .- 交换步骤：
     * .1. prev.next = node2（让前驱节点指向第二个节点）
     * .2. node1.next = node2.next（让第一个节点指向第二个节点的后继）
     * .3. node2.next = node1（让第二个节点指向第一个节点）
     * .- 移动 prev 指针到 node1（交换后的位置）
     * .- 重复上述过程，直到没有足够的节点可以交换
     * .<p>
     * .关键洞察：
     * .1. 使用虚拟头节点可以统一处理头节点的交换，避免特殊情况
     * .2. 交换两个节点需要修改三个指针：前驱节点的 next、node1 的 next、node2 的 next
     * .3. 交换顺序很重要，必须先保存必要的引用，避免丢失节点
     * .4. 每次交换后，prev 指针应该移动到交换后的第二个节点（原来的 node1）
     * .5. 循环条件是 prev.next != null && prev.next.next != null，确保有两个节点可以交换
     * .<p>
     * .图解示例：head = [1,2,3,4]
     * .<p>
     * .初始状态：
     * .dummy → 1 → 2 → 3 → 4 → null
     * .prev
     * .<p>
     * .第一次交换（交换节点 1 和 2）：
     * .<p>
     * .步骤1：标识要交换的节点
     * .dummy → 1 → 2 → 3 → 4 → null
     * .prev   node1 node2
     * .<p>
     * .步骤2：prev.next = node2
     * .dummy ─────→ 2 → 3 → 4 → null
     * .prev    1 ↗  node2
     * .node1
     * .<p>
     * .步骤3：node1.next = node2.next
     * .dummy ─────→ 2 → 3 → 4 → null
     * .prev    1 ─────→ 3
     * .node1   node2
     * .<p>
     * .步骤4：node2.next = node1
     * .dummy ─────→ 2 → 1 → 3 → 4 → null
     * .prev         ↓   ↑
     * .node2  node1
     * .<p>
     * .步骤5：prev = node1（移动到下一对的前驱）
     * .dummy → 2 → 1 → 3 → 4 → null
     * .node2  prev
     * .node1
     * .<p>
     * .第二次交换（交换节点 3 和 4）：
     * .<p>
     * .步骤1：标识要交换的节点
     * .dummy → 2 → 1 → 3 → 4 → null
     * .prev   node1 node2
     * .<p>
     * .步骤2-4：执行交换
     * .dummy → 2 → 1 → 4 → 3 → null
     * .prev
     * .<p>
     * .步骤5：prev = node1
     * .dummy → 2 → 1 → 4 → 3 → null
     * .prev
     * .<p>
     * .最终结果：
     * .2 → 1 → 4 → 3 → null
     * .<p>
     * .详细的指针变化过程：
     * .<p>
     * .原始链表：dummy → 1 → 2 → 3 → 4 → null
     * .<p>
     * .第一轮交换前：
     * .prev = dummy
     * .node1 = 1
     * .node2 = 2
     * .<p>
     * .执行交换：
     * .prev.next = node2        → dummy.next = 2
     * .node1.next = node2.next  → 1.next = 3
     * .node2.next = node1       → 2.next = 1
     * .<p>
     * .结果：dummy → 2 → 1 → 3 → 4 → null
     * .<p>
     * .移动指针：prev = node1 = 1
     * .<p>
     * .第二轮交换前：
     * .prev = 1
     * .node1 = 3
     * .node2 = 4
     * .<p>
     * .执行交换：
     * .prev.next = node2        → 1.next = 4
     * .node1.next = node2.next  → 3.next = null
     * .node2.next = node1       → 4.next = 3
     * .<p>
     * .结果：dummy → 2 → 1 → 4 → 3 → null
     * .<p>
     * .移动指针：prev = node1 = 3
     * .<p>
     * .循环结束条件：prev.next == null（没有更多节点可以交换）
     * .<p>
     * .奇数节点示例：head = [1,2,3]
     * .<p>
     * .初始：dummy → 1 → 2 → 3 → null
     * .<p>
     * .第一次交换：dummy → 2 → 1 → 3 → null
     * .<p>
     * .第二次检查：prev = 1, prev.next = 3, prev.next.next = null
     * .不满足交换条件，循环结束
     * .<p>
     * .结果：2 → 1 → 3 → null（节点 3 保持不变）
     * .<p>
     * .时间复杂度：O(n)，其中 n 为链表长度
     * .- 需要遍历链表一次，每对节点交换一次
     * .<p>
     * .空间复杂度：O(1)
     * .- 只使用了常数个指针变量，没有使用额外的数据结构
     */
    public ListNode swapPairs(ListNode head) {
        // 创建虚拟头节点，简化头节点的处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // prev 指向当前需要交换的两个节点的前一个节点
        ListNode prev = dummyHead;

        // 当存在两个相邻节点可以交换时，继续循环
        while (prev.next != null && prev.next.next != null) {
            // 标识需要交换的两个节点
            ListNode firstNode = prev.next;      // 第一个节点
            ListNode secondNode = prev.next.next; // 第二个节点

            // 执行交换操作（三步）
            // 步骤1：让前驱节点指向第二个节点
            prev.next = secondNode;

            // 步骤2：让第一个节点指向第二个节点的后继
            firstNode.next = secondNode.next;

            // 步骤3：让第二个节点指向第一个节点
            secondNode.next = firstNode;

            // 移动 prev 指针到交换后的第二个节点（原来的 firstNode）
            // 为下一轮交换做准备
            prev = firstNode;
        }

        // 返回新的头节点（虚拟头节点的下一个节点）
        return dummyHead.next;
    }

    public static void main(String[] args) {
        S98_Mid_24_两两交换链表中的节点 solution = new S98_Mid_24_两两交换链表中的节点();

        System.out.println("=== 两两交换链表中的节点测试开始 ===");

        // 测试1: 题目示例1 - [1,2,3,4]
        System.out.println("\n--- 测试1: [1,2,3,4] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - []
        System.out.println("\n--- 测试2: 空链表 [] ---");
        testEmptyList(solution);

        // 测试3: 题目示例3 - [1]
        System.out.println("\n--- 测试3: 单节点 [1] ---");
        testSingleNode(solution);

        // 测试4: 两个节点 [1,2]
        System.out.println("\n--- 测试4: 两个节点 [1,2] ---");
        testTwoNodes(solution);

        // 测试5: 三个节点 [1,2,3]
        System.out.println("\n--- 测试5: 三个节点 [1,2,3] ---");
        testThreeNodes(solution);

        // 测试6: 五个节点 [1,2,3,4,5]
        System.out.println("\n--- 测试6: 五个节点 [1,2,3,4,5] ---");
        testFiveNodes(solution);

        // 测试7: 六个节点 [1,2,3,4,5,6]
        System.out.println("\n--- 测试7: 六个节点 [1,2,3,4,5,6] ---");
        testSixNodes(solution);

        // 测试8: 相同值的节点 [1,1,1,1]
        System.out.println("\n--- 测试8: 相同值的节点 [1,1,1,1] ---");
        testSameValues(solution);

        // 测试9: 大数值 [100,99,98,97]
        System.out.println("\n--- 测试9: 大数值 [100,99,98,97] ---");
        testLargeValues(solution);

        // 测试10: 长链表（10个节点）
        System.out.println("\n--- 测试10: 长链表 [1,2,3,4,5,6,7,8,9,10] ---");
        testLongList(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: [1,2,3,4]
     * .期望输出：[2,1,4,3]
     */
    private static void testCase1(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 2 → 1 → 4 → 3 → null)");

        assert result.val == 2 : "第一个节点应该是2";
        assert result.next.val == 1 : "第二个节点应该是1";
        assert result.next.next.val == 4 : "第三个节点应该是4";
        assert result.next.next.next.val == 3 : "第四个节点应该是3";
        assert result.next.next.next.next == null : "应该只有四个节点";

        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 空链表 []
     * .期望输出：[]
     */
    private static void testEmptyList(S98_Mid_24_两两交换链表中的节点 solution) {
        System.out.print("输入: ");
        printList(null);
        ListNode result = solution.swapPairs(null);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: null)");

        assert result == null : "空链表应该返回null";

        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 单节点 [1]
     * .期望输出：[1]
     */
    private static void testSingleNode(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → null)");

        assert result.val == 1 : "节点值应该是1";
        assert result.next == null : "应该只有一个节点";

        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 两个节点 [1,2]
     * .期望输出：[2,1]
     */
    private static void testTwoNodes(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 2 → 1 → null)");

        assert result.val == 2 : "第一个节点应该是2";
        assert result.next.val == 1 : "第二个节点应该是1";
        assert result.next.next == null : "应该只有两个节点";

        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 三个节点 [1,2,3]
     * .期望输出：[2,1,3]
     */
    private static void testThreeNodes(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 2 → 1 → 3 → null)");

        assert result.val == 2 : "第一个节点应该是2";
        assert result.next.val == 1 : "第二个节点应该是1";
        assert result.next.next.val == 3 : "第三个节点应该是3";
        assert result.next.next.next == null : "应该只有三个节点";

        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 五个节点 [1,2,3,4,5]
     * .期望输出：[2,1,4,3,5]
     */
    private static void testFiveNodes(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 2 → 1 → 4 → 3 → 5 → null)");

        assert result.val == 2 : "第一个节点应该是2";
        assert result.next.val == 1 : "第二个节点应该是1";
        assert result.next.next.val == 4 : "第三个节点应该是4";
        assert result.next.next.next.val == 3 : "第四个节点应该是3";
        assert result.next.next.next.next.val == 5 : "第五个节点应该是5";
        assert result.next.next.next.next.next == null : "应该只有五个节点";

        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 六个节点 [1,2,3,4,5,6]
     * .期望输出：[2,1,4,3,6,5]
     */
    private static void testSixNodes(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 2 → 1 → 4 → 3 → 6 → 5 → null)");

        int[] expected = {2, 1, 4, 3, 6, 5};
        ListNode current = result;
        for (int i = 0; i < expected.length; i++) {
            assert current != null : "节点不应该为null";
            assert current.val == expected[i] : "节点" + (i + 1) + "应该是" + expected[i];
            current = current.next;
        }
        assert current == null : "应该只有六个节点";

        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 相同值的节点 [1,1,1,1]
     * .期望输出：[1,1,1,1]
     */
    private static void testSameValues(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(1);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 1 → 1 → 1 → null)");

        ListNode current = result;
        for (int i = 0; i < 4; i++) {
            assert current != null : "节点不应该为null";
            assert current.val == 1 : "所有节点值应该是1";
            current = current.next;
        }
        assert current == null : "应该只有四个节点";

        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 大数值 [100,99,98,97]
     * .期望输出：[99,100,97,98]
     */
    private static void testLargeValues(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(100);
        head.next = new ListNode(99);
        head.next.next = new ListNode(98);
        head.next.next.next = new ListNode(97);

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 99 → 100 → 97 → 98 → null)");

        assert result.val == 99 : "第一个节点应该是99";
        assert result.next.val == 100 : "第二个节点应该是100";
        assert result.next.next.val == 97 : "第三个节点应该是97";
        assert result.next.next.next.val == 98 : "第四个节点应该是98";

        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 长链表 [1,2,3,4,5,6,7,8,9,10]
     * .期望输出：[2,1,4,3,6,5,8,7,10,9]
     */
    private static void testLongList(S98_Mid_24_两两交换链表中的节点 solution) {
        ListNode head = new ListNode(1);
        ListNode current = head;
        for (int i = 2; i <= 10; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }

        System.out.print("输入: ");
        printList(head);
        ListNode result = solution.swapPairs(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 2 → 1 → 4 → 3 → 6 → 5 → 8 → 7 → 10 → 9 → null)");

        int[] expected = {2, 1, 4, 3, 6, 5, 8, 7, 10, 9};
        current = result;
        for (int i = 0; i < expected.length; i++) {
            assert current != null : "节点不应该为null";
            assert current.val == expected[i] : "节点" + (i + 1) + "应该是" + expected[i];
            current = current.next;
        }
        assert current == null : "应该只有十个节点";

        System.out.println("✓ 测试10通过");
    }

    /**
     * .辅助方法：打印链表
     */
    private static void printList(ListNode head) {
        if (head == null) {
            System.out.print("null");
            return;
        }

        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print(" → ");
            }
            current = current.next;
        }
        System.out.print(" → null");
    }
}

